package com.lfg.leetcode.leetcode0;

public class No72minDistance {

    public static void main(String[] args) {
        int ret = minDistance("intention","execution");
        System.out.println("[" + ret + "]");
    }

    public static int minDistance(String word1, String word2) {
        int length2 = word2.length();
        if ("".equals(word1)) {
            return length2;
        }
        int length1 = word1.length();
        if ("".equals(word2)) {
            return length1;
        }
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = length2; i >= 0; i--) {
            dp[0][i] = i;
        }
        for (int i = length1; i >= 0; i--) {
            dp[i][0] = i;
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j], dp[i][j + 1]) + 1;
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + 1);
                }
            }
        }
        return dp[length1][length2];
    }


    public static int minDistance2(String word1, String word2) {
        if ("".equals(word1)) {
            return word2.length();
        }
        if ("".equals(word2)) {
            return word1.length();
        }
        if (word1.charAt(0) == word2.charAt(0)) {
            return minDistance2(word1.substring(1), word2.substring(1));
        }
        return Math.min(minDistance2(word1.substring(1), word2) + 1,
                Math.min(minDistance2(word1, word2.substring(1)) + 1, minDistance2(word1.substring(1), word2.substring(1)) + 1));
    }
}

